In the field of data communications, an important and often needed function is to determine within a threshold the number of non-fragmented packets ready for transmission from a device. The process of finding the maximum number of non-fragmented packets in a list of packets that fit under a threshold is referred to as “non-fragmentation”. In one non-limiting example, determining the non-fragmentation allows a system to perform quality of service (QoS) functions such as shaping on a list of packets. Non-fragmentation is particularly complicated in Ethernet communications because the Ethernet communications specification does not allow transmission of fragmented packets and because Ethernet packets have variable length. On the other hand, non-fragmentation is not complicated in communication systems where transmission of fragmented packets is allowed or in communications such as asynchronous transmission mode (ATM) since ATM packets have fixed lengths.
Background information and the need for non-fragmentation (in the context of EPON ONU devices, both 1G and 10G) can be found in U.S. patent application Number 20080181248 to Haran et al., “Methods for Dynamic Bandwidth allocation and Queue Management in Ethernet Passive Optical Networks”. Haran teaches conventional methods for dynamic bandwidth allocation and queue management designed to avoid fragmentation loss and guarantee that a length of grant issued by an optical line terminal (OLT) will match precisely the count of bytes to be transmitted by an optical networking unit (ONU).
Note that in the present document an Ethernet passive optical network (EPON) is often used as a non-limiting example of a system in which non-fragmentation is necessary. In the present context of this document, transmission of quantities of data is generally discussed in terms of bytes, or as is generally done in this field, discussed in the equivalent terms of bandwidth or transmission time.
Referring to FIG. 1, a diagram showing an example of timing of communications in an EPON, a centralized network device (OLT) 414 communicates with one or more user devices (ONUs) 900. In the diagram time progresses from left to right, communications from the OLT to the ONUs are shown above the time line (TIME), and communications from the ONUs to the OLT are shown below the time line. A report R1 from a first ONU notifies the OLT 414 that the first ONU has data to send to the OLT and how much data the first ONU wants to send (known as requested allocation). The OLT sends a gate G1 to the first ONU with a granted allocation (how much data the first ONU is allowed to send) of time starting at T1 at which the first ONU is to send data D1. Similarly, a report R2 from a second ONU notifies the OLT 414 that the second ONU has data to send to the OLT and how much data the second ONU wants to send. The OLT knows the amount of time allocated to the first ONU to send data D1 and can send a gate G2 to the second ONU with a granted allocation of time starting at time T2 at which the first ONU's time allocation will be complete and the second ONU can send data D2.
Referring to FIG. 2, a diagram showing an example of a queue egress process, a plurality of queues in an ONU (SUB-QUEUE 0, SUB-QUEUE 1, SUB-QUEUE 2) contain packets (P1-P14) of varying lengths. When a granted bandwidth allocation is applied as a threshold (THRESHOLD) across the queue equally to all sub-queues, the threshold is sufficient to include the full packets P1, P2, P3, P4, P5, and P6 which are transmitted. Packets P7 and P9 would have to be fragmented to be transmitted, as there is not enough granted allocation in the bandwidth allocation scheme for the entire packets to be transmitted, and hence packets P7 and P9 are not transmitted. The difference between the granted bandwidth and the number of bytes transmitted is wasted bandwidth. In order to avoid wasted bandwidth, a better method of transmission is to determine the non-fragmentation, and request a threshold equal to the number of bytes in the non-fragmented packets.
Referring to FIG. 3, a diagram of a conventional technique for determining non-fragmentation on a single queue, a list 902 of packet lengths is needed. The list of packet lengths 902 is also known as a lengths memory. In the present context, the letter “B” with a number is generally used as a non-limiting example to represent the length of a packet in bytes, and for convenience can also be used to refer to the packet. In the context of the present document, ingress refers to a packet that has been prepared for transmission coming into a module for storage and egress. In the context of the present document, egress refers to a packet going out of a storage module for transmission. Packets 84B, 250B, and 88B have exemplary lengths of 84 Bytes, 250 Bytes, and 88 Bytes, respectively. Time flows from left to right in the direction of the arrow TIME, showing ingress of a first packet 84B into a packet memory (not shown). The length of packet 84B is stored in lengths memory 902 in a first memory location M0, with an association to the location in the packet memory of packet 84B. Similarly, a second packet 250B ingresses into the packet memory (not shown). The length of packet 250B is stored in lengths memory 902 in a second memory location M1. A third packet 88B ingresses into the packet memory (not shown) and the length of packet 88B is stored in lengths memory 902 in memory location M2. A conventional non-fragmentation engine (abbreviated as “NoF( )”) crawls the lengths memory starting at a designated memory location, and builds a sum of the list elements (packet lengths) until a given threshold has been exceeded. Once the threshold has been exceeded, the previous sum of the elements is the non-fragmentation results. In a non-limiting example, the given threshold is 400 Bytes, and the NoF( ) starts summing at memory location M0. The sum of packet lengths M0 and M1, shown as SUM1=84 B+250 B=334 B. The NoF( ) continues summing by adding M2 to the current sum, shown as SUM2=334 B+88 B=422 B. 422 Bytes exceeds the threshold of 400 Bytes, so the previous sum of 334 Bytes is used as the NoF( ) result.
Note that the term threshold can be used in different, but related functions. In one context, when an ONU wants to determine NoF( ) for an allocation request, the threshold is the committed bandwidth (Bytes) configured by the service level agreement. In one non-limiting example, the committed service level agreement is 8 Mbps (mega bit per second) which is 1 MB per second (mega byte per second) where in a system of 1000 allocation requests per second the threshold will be 1000 Bytes per second, so the NoF(1000) needs to be determined and sent for an allocation request. In another context, when an ONU is granted an allocation, the allocation grant is the threshold used in determining NoF( ) to know how many packets can be egressed. In one non-limiting example, based on system loading an OLT may grant an allocation of 1000 Bytes to an ONU. The NoF(1000) needs to be determined to know how many packets can be egressed. In a case where an allocation grant to an ONU is the allocation request, the previously determined NoF( ) can be used.
Conventional non-fragmentation engine techniques are limited due to factors such as computational complexity, memory requirements, and processing time. The complexity of conventional non-fragmentation techniques for one queue is O(N), where N is the number of packets in the queue. The memory requirements for the lengths memory can be computed from the memory size allocated for storing packets (PacketsMemSize) divided by the minimum packet size (MinPacketSize):PacketsMemSize/MinPacketSize=LengthsMemSize
A non-limiting example of conventional non-fragmentation operating characteristics is the case supporting a maximum threshold of 1.3 Mbytes, using a PacketsMemSize of 64 MB, and packet lengths in the range of [84 . . . 2020]. Note these are real numbers of EPON packets with preamble and IPG when supporting basic packets lengths of [64 . . . 2000]. The complexity of this case is the maximum number of packets that can fit within the threshold, calculated by the threshold divided by the minimum packet length, approximately 1.3 MB/84 B=15.5K, meaning the NoF( ) would need to crawl up to 15.5K times, or in other words calculate up to 15.5K sums. A lengths memory needs to be allocated to hold the lengths of all of the packets in the packets memory (in other words the number of elements in the list could maximally be) the PacketsMemSize divided by the minimum packet length, approximately 64 MB/84 B=780K elements (also known as entries). If each element is an 11 bit number, the amount of memory needed for the lengths memory is 780K*11 bits=1.07 MB.
For conventional 1G EPON systems PacketsMemSize per queue is small, so total memory size is small. Requirements for future systems require a larger PacketMemSize, with a corresponding increase in cost. State of the art ASIC memory costs (45 nm process) for a 1.07 MB memory is approximately one USA dollar (SUSD 1).
Calculations typically need to be completed in approximately 1000 clock cycles. For conventional 1G EPON systems the threshold was limited to a maximum of approximately 0.13 MB, requiring approximately 1500 clock cycles, which was acceptable. Using the above exemplary case where 15.5K crawls (sum calculations) are needed, even if 4 elements can be summed per clock cycle, there is not sufficient processing time to perform the necessary calculations.
This above non-limiting example and typical operating characteristics demonstrates the limitations of conventional non-fragmentation techniques. The complexity of O(N) is too big for advanced communication systems, large memory requirements are cost prohibitive to implement, and long processing times are not available for performing the necessary calculations.
There is therefore a need for a system and method for determining non-fragmentation for communication of packets having reduced complexity, lower memory requirements, and shorter processing time.